DROPS

Document

DOI: 10.4230/OASIcs.WCET.2023.7

Constant-Loop Dominators for Single-Path Code Optimization

Authors: Emad Jacob Maroun, Martin Schoeberl, and Peter Puschner

Published in: OASIcs, Volume 114, 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)

Abstract

Single-path code is a code generation technique specifically designed for real-time systems. It guarantees that programs execute the same instruction sequence regardless of runtime conditions. Single-path code uses loop bounds to ensure all loops iterate a fixed number of times equal to their upper loop bound. When the lower and upper bounds are equal, the loop must iterate the same number of times, which we call a constant loop. In this paper, we present the constant-loop dominance relation on control-flow graphs. It is a variation of the traditional dominance relation that considers constant loops to find basic blocks that are always executed the same number of times. Using this relation, we present an optimization that reduces the code needed to manage single-path code. Our evaluation shows significant performance improvements, with one example of up to 90%, with mostly minor effects on code size.

Cite as

Emad Jacob Maroun, Martin Schoeberl, and Peter Puschner. Constant-Loop Dominators for Single-Path Code Optimization. In 21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023). Open Access Series in Informatics (OASIcs), Volume 114, pp. 7:1-7:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{maroun_et_al:OASIcs.WCET.2023.7,
  author =	{Maroun, Emad Jacob and Schoeberl, Martin and Puschner, Peter},
  title =	{{Constant-Loop Dominators for Single-Path Code Optimization}},
  booktitle =	{21th International Workshop on Worst-Case Execution Time Analysis (WCET 2023)},
  pages =	{7:1--7:13},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-293-8},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{114},
  editor =	{W\"{a}gemann, Peter},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.WCET.2023.7},
  URN =		{urn:nbn:de:0030-drops-184361},
  doi =		{10.4230/OASIcs.WCET.2023.7},
  annote =	{Keywords: single-path, dominators, algorithms, optimization, control-flow graph}
}

Search Results

Documents authored by Maroun, Emad Jacob

Constant-Loop Dominators for Single-Path Code Optimization

Abstract

Cite as

Thanks for your feedback!

Could not send message